//package com.waiting.leetcode;
//
//import java.util.*;
//
///**
// * @Description 图的遍历
// * @Author bjweitingting
// * @Date 2019/3/21
// **/
//class Node2 {
//    public int val;
//    public List<Node> neighbors;
//
//    public Node() {
//    }
//
//    public Node(int _val, List<Node> _neighbors) {
//        val = _val;
//        neighbors = _neighbors;
//    }
//};
//
//public class CloneGraph133 {
//
//    Map<Node, Node> seen = new HashMap<>();
//
//    //深度优先，DFS算法
//    public Node cloneGraph(Node node) {
//        if (seen.containsKey(node))
//            return seen.get(node);
//        Node cloneNode = new Node(node.val, new ArrayList<>());
//        seen.put(node, cloneNode);
//        for (Node temp : node.neighbors) {
//            cloneNode.neighbors.add(cloneGraph(temp));
//        }
//        return cloneNode;
//    }
//
//    //广度优先
//    public Node cloneGraph2(Node node) {
//        if (node == null) {
//            return node;
//        }
//
//        ArrayList<Node> nodes = getNodes(node);
//
//        Map<Node, Node> mapping = new HashMap<>();
//
//        for (Node n : nodes) {
//            mapping.put(n, new Node(n.val, new ArrayList<Node>()));
//        }
//
//        for (Node n : nodes) {
//            Node newNode = mapping.get(n);
//            for (Node neighbor : n.neighbors) {
//                Node newNeighbor = mapping.get(neighbor);
//                newNode.neighbors.add(newNeighbor);
//            }
//        }
//        return mapping.get(node);
//    }
//
//    private ArrayList<Node> getNodes(Node node) {
//        Queue<Node> queue = new LinkedList<>();
//        Set<Node> set = new HashSet<>();
//
//        queue.offer(node);
//        set.add(node);
//        while (!queue.isEmpty()) {
//            Node head = queue.poll();
//            for (Node neighbor : head.neighbors) {
//                if (!set.contains(neighbor)) {
//                    set.add(neighbor);
//                    queue.offer(neighbor);
//                }
//            }
//        }
//        return new ArrayList<Node>(set);
//    }
//}
